package com.hdu.random;

public class lc221 {
    class Solution {
        public int maximalSquare(char[][] matrix) {
            int row = matrix.length;
            int col = matrix[0].length;
            int[][] dp = new int[row][col];
            int ans = 0;
            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    if (matrix[i][j] == '1')
                    {
                        if (i == 0 || j == 0) dp[i][j] = 1;
                        else
                        {
                            int p1 = dp[i - 1][j];
                            int p2 = dp[i][j - 1];
                            int p3 = dp[i - 1][j - 1];
                            dp[i][j] = Math.min(p1, Math.min(p2, p3)) + 1;
                        }
                        ans = Math.max(ans, dp[i][j]);
                    }
                }
            }
            return ans * ans;
        }
    }
}
